package com.peng.leetcode.array;

/**
 * MaxSubArray
 * 53. 最大子数组和
 * https://leetcode.cn/problems/maximum-subarray/
 *
 * @author: lupeng6
 * @create: 2023/2/15 13:50
 */
public class MaxSubArray {
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        return max(nums, 0, nums.length - 1);
    }

    private int max(int[] nums, int l, int r) {
        if (l == r) {
            return nums[l];
        }
        int mid = l + (r - l) / 2;
        return max3(max(nums, l, mid), max(nums, mid + 1, r), cal(nums, l, mid, r));
    }

    private int cal(int[] nums, int l, int mid, int r) {
        int sum = 0;
        int leftSum = Integer.MIN_VALUE;
        for (int i = mid; i >= l; i--) {
            sum += nums[i];
            if (sum > leftSum) {
                leftSum = sum;
            }
        }

        sum = 0;
        int rightSum = Integer.MIN_VALUE;
        for (int i = mid + 1; i <= r; i++) {
            sum += nums[i];
            if (sum > rightSum) {
                rightSum = sum;
            }
        }
        return leftSum + rightSum;
    }

    private int max3(int i1, int i2, int i3) {
        return Math.max(Math.max(i1, i2), i3);
    }
}
